/*************************************************************************
	> File Name: treeSample.cpp
	> Author:Ryan 
	> Mail: 
	> Created Time: Sun Oct 11 10:35:22 2020
 ************************************************************************/

#include<iostream>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
/* 
 *node of the tree  
 */
struct BTreeNode{
    int val;
    BTreeNode *LChild;
    BTreeNode *RChild;
    BTreeNode(int val):val(val),LChild(NULL),RChild(NULL){} 
};
/*
 *BTree 
 */ 
class BTree{
    private:
        BTreeNode *root;
        int n;
    public:
        BTree():root(NULL){}
        BTree(vector<int>);//bulid tree
        
        void createTree(vector<int>,BTreeNode *&);//build the tree in preorder by recursion
        
        void show();//show the tree by recursion
        void showTree(BTreeNode*);//show the tree in preorder by recursion
        void showTree1(BTreeNode*);//show the tree in midorder by recursion
        void showTree2(BTreeNode*);//show the tree in postorder by recursion

        void show1();//show the tree not by recursion
        void showTree3(BTreeNode*);//show the tree in preorder not by recursion
        void showTree4(BTreeNode*);//show the tree in midorder not by recursion
        void showTree5(BTreeNode*);//show the tree in postorder not by recursion
        
        void show2();    
        void show_lT(BTreeNode*); //show the tree's level_traversal
};     
/*
 *build the tree in preorder 
 */ 
BTree::BTree(vector<int> num){
    n=0;
    createTree(num,root);
}
void BTree::createTree(vector<int> num,BTreeNode *&node){
    if(num.size()>=n+1&&num[n]!=-1){
        node = new BTreeNode(num[n++]);
        createTree(num,node->LChild);
        createTree(num,node->RChild);
    }
    else{
        n++;
    }   
}

/*
 *show the tree by recursion 
 */ 
 void BTree::show(){
    /*show in preorder*/
    cout<<"Here shows in preorder by recursion"<<endl;
    showTree(root);
    cout<<endl;

    /*show in midorder*/ 
    cout<<"Here shows in midorder by recursion"<<endl;
    showTree1(root);
    cout<<endl;
    
    /*show in postorder*/
    cout<<"Here shows in postorder by recursion"<<endl;
    showTree2(root);
    cout<<endl;
}

/*
 *show in preorder by recursion
 */ 
void BTree::showTree(BTreeNode *node){
    if(node!=NULL){
        cout<<node->val;
        showTree(node->LChild);
        showTree(node->RChild);
    }
}

/*
 *show in midorder by recursion
 */ 
void BTree::showTree1(BTreeNode *node){
    if(node!=NULL){
        showTree1(node->LChild);
        cout<<node->val;
        showTree1(node->RChild);
    }
}

/*
 *show in postorder by recursion
 */ 
void BTree::showTree2(BTreeNode *node){
    if(node!=NULL){
        showTree2(node->LChild);
        showTree2(node->RChild);
        cout<<node->val;
    }
}

/*
 *show the tree not by recursion
 */ 
 void BTree::show1(){
    
    /*show in preorder*/
    cout<<"Here shows in preorder"<<endl;
    showTree3(root);
    cout<<endl;

    /*show in midorder*/ 
    cout<<"Here shows in midorder"<<endl;
    showTree4(root);
    cout<<endl;
    
    /*show in postorder*/
    cout<<"Here shows in postorder"<<endl;
    showTree5(root);
    cout<<endl;
 }
/*
 *show in preorder
 */ 
void BTree::showTree3(BTreeNode *node){
    stack<BTreeNode*> s;
    if(node!=NULL) s.push(node);

    while(!s.empty()){
        BTreeNode *tmp = s.top();s.pop();
        cout<<tmp->val;
        if(tmp->RChild!=NULL) s.push(tmp->RChild);
        if(tmp->LChild!=NULL) s.push(tmp->LChild);
    }
}
/*
 *show in midorder
 */ 
void BTree::showTree4(BTreeNode *node){
    BTreeNode *p = node;
    stack<BTreeNode*> s;

    while(1){
        if(p->LChild!=NULL){ 
            s.push(p);
            p = p->LChild;
        }
        else if(!p->LChild){
            cout<<p->val;
            if(p->RChild!=NULL) {p=p->RChild;continue;}
            while(!s.empty()&&!p->RChild){
                p = s.top();s.pop();
                cout<<p->val;
            }
            if(p->RChild!=NULL) p=p->RChild;
            else if(p->RChild==NULL) break;
        }
    }
}

/*
 *show in postorder
 */ 
void BTree::showTree5(BTreeNode *node){
    cout<<"不想敲，可以参考网址：https://www.cnblogs.com/SHERO-Vae/p/5800363.html"<<endl;
}

/*
 *show the tree's level_traversal
 */ 
 void BTree::show2(){
    cout<<"Here's level_traversal"<<endl;
    show_lT(root);
    cout<<endl;
 }

 void BTree::show_lT(BTreeNode *node){
    queue<BTreeNode*> q;
    if(node!=NULL) q.push(node);
    
     BTreeNode *tmp;
     while(!q.empty()){
         tmp = q.front();q.pop();
         cout<<tmp->val;
         if(tmp->LChild!=NULL) q.push(tmp->LChild);
         if(tmp->RChild!=NULL) q.push(tmp->RChild);
     }
 }

int main(){
    vector<int> tmp {1,2,-1,-1,3,4,-1,-1,5,6,-1,-1,7,-1,-1};
    BTree *btree = new BTree(tmp);
    btree->show();
    btree->show1();
    btree->show2();
}


